//给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语
//的小写字母。如果没有不包含相同字符的一对字符串，返回 0。 
//
// 
//
// 示例 1： 
//
// 
//输入：words = ["abcw","baz","foo","bar","fxyz","abcdef"]
//输出：16 
//解释：这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。 
//
// 示例 2： 
//
// 
//输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
//输出：4 
//解释：这两个单词为 "ab", "cd"。 
//
// 示例 3： 
//
// 
//输入：words = ["a","aa","aaa","aaaa"]
//输出：0 
//解释：不存在这样的两个单词。
// 
//
// 
//
// 提示： 
//
// 
// 2 <= words.length <= 1000 
// 1 <= words[i].length <= 1000 
// words[i] 仅包含小写字母 
// 
//
// 
//
// 
// 注意：本题与主站 318 题相同：https://leetcode-cn.com/problems/maximum-product-of-word-
//lengths/ 
//
// Related Topics 位运算 数组 字符串 👍 152 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2025-01-08 23:31:50
 * @description LCR 005.最大单词长度乘积
 */
public class AseY1I{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 AseY1I fun=new AseY1I();
	 	 Solution solution = fun.new Solution();
		 System.out.println(((1<<1)&(1<<1)));
		 solution.maxProduct(new String[]{"a","ab","abc","d","cd","bcd","abcd"});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //计算每个字符串的掩码。对应26位，有则是1，否则是0
		//遍历o n^2，如果&是0，计算长度，
			//可以用map存下每个掩码的最长长度
    public int maxProduct1(String[] words) {
		Map<Integer,Integer> ma=new HashMap<>();
		List<Integer> mask=new ArrayList<>();
		for (String word : words) {
			int maskNum = mask(word);
			mask.add(maskNum);
			ma.put(maskNum, Math.max(ma.getOrDefault(maskNum, 0), word.length()));
		}
		int res=0;
		for (int i = 0; i < mask.size(); i++) {
			for (int j = i+1; j < mask.size(); j++) {
				if(((mask.get(i))&(mask.get(j)))==0){
					res=Math.max(res,ma.get(mask.get(i))*ma.get(mask.get(j)));
				}
			}
		}
		return res;
    }
	private int mask(String word){
		int res=0;
		for (char c : word.toCharArray()) {
			res|=(1<<(c-'a'));
		}
		return res;
	}
	public int maxProduct(String[] words) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		int length = words.length;
		for (int i = 0; i < length; i++) {
			int mask = 0;
			String word = words[i];
			int wordLength = word.length();
			for (int j = 0; j < wordLength; j++) {
				mask |= 1 << (word.charAt(j) - 'a');
			}
			if (wordLength > map.getOrDefault(mask, 0)) {
				map.put(mask, wordLength);
			}
		}
		int maxProd = 0;
		Set<Integer> maskSet = map.keySet();
		for (int mask1 : maskSet) {
			int wordLength1 = map.get(mask1);
			for (int mask2 : maskSet) {
				if ((mask1 & mask2) == 0) {
					int wordLength2 = map.get(mask2);
					maxProd = Math.max(maxProd, wordLength1 * wordLength2);
				}
			}
		}
		return maxProd;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
